# 205. 同构字符串
#
# 给定两个字符串 s 和 t ，判断它们是否是同构的。
# 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
# 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
#
# 时间复杂度：O(n)，其中 n 为字符串的长度。我们只需同时遍历一遍字符串 s 和 t 即可。
# 空间复杂度：O(∣Σ∣)，其中 Σ 是字符串的字符集。
# 哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要 O(∣Σ∣) 的空间。
def isIsomorphic(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    index = 0
    re = True
    # 使用两张 hash 表保存字典
    char_dict_s = {}
    char_dict_t = {}
    while re and index < len(s):
        s_char = s[index]
        t_char = t[index]

        temp_re_s = True
        temp_re_t = True
        # 判断 hashtable 中是否存在 key
        # 1）不存在，存入字典
        # 2）存在，比较
        dict_s = char_dict_s.get(s_char)
        dict_t = char_dict_t.get(t_char)

        if dict_s is None:
            char_dict_s[s_char] = t_char
        else:
            temp_re_s = dict_s == t_char

        if dict_t is None:
            char_dict_t[t_char] = s_char
        else:
            temp_re_t = dict_t == s_char

        re = temp_re_s and temp_re_t

        index += 1

    return re


result = isIsomorphic('add', 'foo')
print(f"result:{result}")

result = isIsomorphic('badc', 'baba')
print(f"result:{result}")
